package me.algo.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/18
 */
public class T3 {
    public static void main(String[] args) {
        HashMap<Integer, Character> map = new HashMap<>();
        for (int i = 0; i <= 25; i++) {
            map.put(i, (char) ((int) 'a' + i));
        }
        System.out.println(map);
    }


    /**
     * 988. 从叶结点开始的最小字符串
     * @param root
     * @return
     */
    public static String smallestFromLeaf(TreeNode root) {
        if (Objects.isNull(root)) {
            return "";
        }
        String min = null;
        LinkedList<Pair> que = new LinkedList<>();
        que.addLast(new Pair(root, ""));
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                size--;
                Pair pa = que.removeFirst();
                TreeNode node = pa.node;
                if (node.right == null && node.left == null) {
                    // 找到一个字符串
                    int val = node.val;
                    Character c = MAP.get(val);
                    String s = c + pa.str;
                    if (min == null) {
                        // 如果是第一字符串  直接赋值
                        min = s;
                    } else if (min.compareTo(s) > 0) {
                        min = s;
                    }
                    continue;
                }
                if (node.right != null) {
                    int val = node.val;
                    Character c = MAP.get(val);
                    Pair rpa = new Pair(node.right, c + pa.str);
                    que.addLast(rpa);
                }
                if (node.left != null) {
                    int val = node.val;
                    Character c = MAP.get(val);
                    Pair lpa = new Pair(node.left, c + pa.str);
                    que.addLast(lpa);
                }
            }
        }

        return min;
    }

    static HashMap<Integer, Character> MAP = new HashMap<>();
    static {
        for (int i = 0; i <= 25; i++) {
            MAP.put(i, (char) ((int) 'a' + i));
        }
    }

    static class Pair {
        TreeNode node;
        String str;

        public Pair(TreeNode node, String str) {
            this.node = node;
            this.str = str;
        }
    }
}
